package leetcode每日一题.leetcode20212;

/**
 * 1. 问题描述
 *      给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，
 *      总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
 *
 * 2. 算法分析
 *      1. 暴力
 *      2. 滑动窗口
 *
 *      leetcode相关题目：1004,1208,1493
 *
 *
 *      思路分析：(目前没有想明白)
 *          1. 考虑最特殊的情况即k = 0，此时就是找到字符串中的出现的连续子字符串的最大长度
 *             不需要考虑替换
 *
 *          2. 如果当k > 0的情况，此时有字符的替换，该如何思考? 主要是考虑如何移动窗口?
 *             我们的替换策略就是：每次替换掉窗口内出现次数最多的字符之外的元素，因为只有这样才能保证
 *             替换后的重复连续字符串最长
 *
 *             算法伪代码：
 *                  通过一个hash表记录当前窗口中字符出现的次数，使用maxCount记录当前窗口中出现做多字符的次数
 *                  ，此外定义左右窗口left，right构成一个[left,right]或者[left,right)的窗口，下面的代码采
 *                  用的是左闭右开的窗口即[left,right)
 *
 *                  由于定义了最多替换的个数为k个，则窗口中出现次数最多的字符个数maxCount+k就是当前窗口可以找到
 *                  的最大连续重复字符串的长度，此时我们需要比较窗口的长度right - left与maxCount + k之间的关系
 *                  如果maxCount + k >= right - left,说明此时我们还是可以继续移动right来扩大最长重复字符串，
 *                  否则此时我们不能继续扩张右窗口，此时我们需要左窗口，来重新下一次的寻找
 *
 *                  关键：left和right维护的窗口始终是历史最大的连续重复字符串的长度，注意是长度，而不是最大重复
 *                  连续字符串，因为此时[left,right)对应的窗口的子串未必是替换之后最大连续重复子字符串(因为right
 *                  最终会移动到len的位置)，我们可以通过若干案例来理解
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q02_替换后的最长重复字符 {

    public static void main(String[] args) {
        System.out.println(LongestRepeatSubStringLength("ABBACAABBBCCCCAD"));
    }

    // 滑动窗口
    public static int characterReplacement(String s, int k) {
        int len = s.length();
        if(len < 2) {
            return len;
        }

        char[] charArray = s.toCharArray();
        int maxCount = 0; // 记录窗口中出现次数最多的字符的次数

        // 定义左右窗口
        int left = 0;
        int right = 0;

        // 定义频数数组
        int[] freq = new int[26];

        // 扫描右窗口
        while(right < len) {
            // 1. right指向的当前字符进入窗口
            freq[charArray[right] - 'A']++; // 当前字符的频数+1

            // 2. 更新当前窗口中出现次数最多的字符的次数
            maxCount = Math.max(maxCount,freq[charArray[right] - 'A']);

            right++; // 移动右窗口

            // 3. 判断当前窗口替换字符之后的的长度与窗口的长度
            if(right - left > maxCount + k) {
                // 如果当前窗口的长度严格大于当前窗口出现次数最多的字符的次数 + 可以替换的次数
                // 移动左窗口
                freq[charArray[left] - 'A']--; // 因为出了窗口所以频数-1
                left++;
            }
        }

        return right - left;
    }

    // 考虑k = 0的情况，找到字符串中的最长重复字符串的长度
    public static int LongestRepeatSubStringLength(String s) {
        int len = s.length();
        if (len < 2) {
            return len;
        }
        char[] chars = s.toCharArray();
        // 定义窗口
        int left = 0;
        int right = 0;
        int maxLen = 0; // 记录全局的最大连续长度
        while (right < len) {
            if (chars[right] == chars[left]) {
                right++;
            } else {
                left++;
            }
            maxLen = Math.max(maxLen,right - left);
        }
        return maxLen;
    }
}
